Các thổ dân của lãnh thổ Vladivostok ngày nay là người dân tộc thiểu số Udege, và một tiểu dân tộc thiểu số được gọi là Taz trong đó nổi lên thông qua các thành viên của người Udege bản địa lai với người Trung Quốc gần đó và người Nanai. Khu vực này đã là một phần của nhiều quốc gia, chẳng hạn như Mohe, Balhae, Goguryeo, nhà Tấn, nhà Nguyên, và các thế lực Hàn Quốc, Trung Quốc khác, trước khi Nga mua lại toàn bộ các tỉnh hàng hải và đảo Sakhalin bởi Hiệp ước Bắc Kinh (1860). Nhà Thanh, vừa bị thua trong cuộc chiến tranh nha phiến với Anh, không thể bảo vệ khu vực này. Bờ biển Thái Bình Dương gần Vladivostok đã được người Trung Quốc và Mãn Châu đến định cư trong thời nhà Thanh. Một tàu săn cá voi Pháp đến thăm Vịnh Golden Horn năm 1852 đã phát hiện ra làng của những ngư dân Trung Quốc và Mãn Châu trên bờ của nó. Người Mãn Châu cấm người Hán đến hầu hết vùng Mãn Châu bao gồm khu vực Vladivostok - nó chỉ được những kẻ khai thác hải sâm bất hợp pháp ghé đến.

Ngày 20 tháng sáu (2 tháng 7 theo dương lịch), năm 1860, tàu quân sự Manchur, dưới sự chỉ huy của thuyền trưởng-Trung Alexey K. Shefner, được gọi đến Vịnh Golden Horn để lập ra một tiền đồn được gọi là Vladivostok. Bảo đảm đốc Nikolay Komarov với 28 binh sĩ và hai hạ sĩ quan dưới quyền chỉ huy của ông đã được đưa từ Nikolayevsk-on-Amur bằng tàu để xây dựng các tòa nhà đầu tiên của thành phố trong tương lai.

Chiến tranh Manza năm 1868 là nỗ lực đầu tiên của Nga trục xuất vùng này khỏi lãnh thổ của Trung Quốc. Chiến sự nổ ra xung quanh Vladivostok khi người Nga cố gắng ngăn chặn hoạt động khai thác vàng và trục xuất các công nhân Trung Quốc ở đó. Người Trung Quốc đã chống lại một nỗ lực của Nga nhằm chiếm đảo Ashold, hai trạm quân sự của Nga và ba thị trấn Nga bị tấn công bởi người Trung Quốc, Nga và thất bại trong việc lật đổ Trung Quốc.

Một hệ thống phức tạp của công sự được xây dựng giữa những năm 1870 và 1890. Một đường dây điện báo từ Vladivostok đến Thượng Hải và Nagasaki đã được khánh thành vào năm 1871, năm mà một cảng biển thương mại được chuyển vào đây từ Nikolayevsk-on-Amur. Thành thị trấn đã được cấp vào 22 tháng 4 năm 1880. Một huy hiệu có hình hổ Siberia, đã được thông qua tháng 3 năm 1883

Các trường trung học đầu tiên được mở cửa vào năm 1899. Nền kinh tế của thành phố đã tăng trưởng trong năm 1903, với việc hoàn thành các tuyến đường sắt xuyên Siberia kết nối Vladivostok đến Moskva và châu Âu. Trong sự trỗi dậy của Cách mạng Tháng Mười, Vladivostok là có tầm quan trọng về quân sự lớn cho Cộng hòa Viễn Đông, Chính phủ Priamurye tạm thời, và sự can thiệp của quân đồng minh, bao gồm quân đội nước ngoài từ Nhật Bản, Hoa Kỳ, Canada, Tiệp Khắc, và các quốc gia khác. 1.600 quân Trung Quốc cũng đã can thiệp để đáp ứng với yêu cầu của cộng đồng người Trung Quốc trong khu vực để hỗ trợ tham gia của thành phố của Hồng quân Ieronim Uborevich của trên 25 Tháng Mười năm 1922, chấm dứt cuộc nội chiến Nga..

Là căn cứ hải quân chính của Hạm đội Thái Bình Dương của Liên Xô, Vladivostok đã chính thức đóng cửa cho người nước ngoài trong những năm thuộc Liên Xô. Thành phố đã tổ chức hội nghị thượng đỉnh mà Leonid Brezhnev và Gerald Ford đã tiến hành các cuộc đàm phán Giới hạn Vũ khí Chiến lược vào năm 1974. Vào thời điểm đó, hai nước đã quyết định hạn chế số lượng trên các hệ thống vũ khí hạt nhân khác nhau và cấm xây dựng mới các máy phóng ICBM trên đất liền.

Trong năm 2012, Vladivostok tổ chức hội nghị thượng đỉnh APEC 24. Các nhà lãnh đạo từ các nước thành viên APEC gặp nhau tại đảo Russky, ngoài khơi bờ biển của Vladivostok. Với hội nghị thượng đỉnh trên đảo Russky, chính phủ và doanh nghiệp tư nhân khai trương khu nghỉ dưỡng, ăn tối và các cơ sở vui chơi giải trí, ngoài việc cải tạo và nâng cấp sân bay quốc tế Vladivostok. Hai cây cầu dây văng lớn đã được xây dựng để chuẩn bị cho hội nghị thượng đỉnh, cụ thể là các cầu Zolotoy Rog trong Zolotoy Rog Bay ở trung tâm của thành phố, và cầu đảo Russky từ đất liền ra đảo Russky (nó là cầu dây văng dài nhất thế giới hiện nay). Cơ sở mới của Đại học Viễn Đông Liên bang sẽ được hoàn thành trên đảo Russky vào năm 2012.Tháng 9 năm 2014, Vladivostok là nơi tiến hành Diễn đàn kinh tế Phương Đông (Eastern Economic Forum) lần đầu tiên. Đây là một trong những diễn đàn thường niên quan trọng và lớn nhất của Liên bang Nga. Từ đó, diễn đàn này được tổ chức vào tháng 9 hàng năm với mục đích quảng bá và thu hút đầu tư nhằm phát triển kinh tế cho vùng Viễn Đông, phục vụ cho chính sách hướng Đông của chính phủ V.V. Putin.